COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a70.tex[106,phy] \today\hfill}

\bigskip
\line{\bf Case Study: Text Justification\hfill}

A program has read a section of English text, and has stored it in~{\tt S},
of type {\tt STRING80}. The program has removed extraneous spaces at the
left and between words; that is, the text is left justified. There is not
enough room left in~{\tt S} for the next word from the input. We want
to design a procedure to print~{\tt S}, adding enough extra space
between words that the line is also right-justified: i.e., the last
non-blank character is in column~80. We want to add the spaces as
uniformly as possible.

Let's assume that the program has counted the interword spaces and
saved that number in~{\tt A}. It has determined the number of spaces
after the last non-blank character and saved that in~{\tt B}. If
{\tt A=0}, there is no place to add spaces, and we can do nothing
better than

{\obeylines\obeyspaces\let =\ \tt
        FOR I:=1 TO 80-B DO
            WRITE (S[I]);
        WRITELN
}

\noindent
If {\tt A>0}, though, we can enlarge the spaces. We want to expand~{\tt A}
spaces to {\tt A+B}; ideally, each interword space becomes
{\tt (A+B)/A} spaces. That number, though, may not be an integer, and we
can only print integer numbers of spaces.

The next best thing is to try to keep the cumulative number of spaces in the output
as close as possible to {\tt (A+B)/A} times the number in the input.
The program can process the characters in {\tt S[1..80-B]}, printing the
non-blank ones. On encountering a space, the program counts it in
variable~{\tt C}, and prints enough spaces that the total number of
output spaces is close to {\tt C(A+B)/A}. There are several ways to do this:

\smallskip
\disleft 20pt:(1):
Let the cumulative number of output spaces be {\tt TRUNC(C*(A+B)/A)},
or simply \hbox{\tt C*(A+B) DIV A}. Either keep track in a variable of
the number of previous output spaces, or output the change in the above
formula between~{\tt C} and~{\tt C-1}: {\tt C*(A+B) DIV A-(C-1)*(A+B)
DIV A}.
Notice that when the last input space comes along, {\tt C=A}, so the
number of output spaces is correctly brought to {\tt A+B}. Confirm
that (since {\tt B >= 0}), every input space gives rise to
at least one output space.

\smallskip
\disleft 20pt:(2):
Keep track of the deficiency of output spaces, in units of {\tt 1/A}.
Use an integer variable~{\tt D}. Every input space will increase this deficiency
by {\tt A+B}; every output space decreases it by~{\tt A}. On encountering
a space in~{\tt S}, the program does this:

{\obeylines\obeyspaces\let =\ \tt
        D:=D+(A+B);

        WHILE D>=A DO
            BEGIN
            WRITE('\spa');
            D:=D-A
            END;
}

\vfill\eject

%\smallskip
\disleft 20pt:(3):
Let {\tt Q=(A+B) DIV A=TRUNC((A+B)/A)}, {\tt R=(A+B) MOD A}. If
every input space gave rise to {\tt Q}~output spaces, there would be a
deficiency of {\tt (A+B)-Q*A=R} spaces, so let the first {\tt R}~input
spaces give rise to {\tt Q+1} output spaces. The relevant part of the
program is

{\obeylines\obeyspaces\let =\ \tt
        IF S[I]='\spa' THEN
            BEGIN
            C:=C+1;
            FOR J:=1 TO Q DO WRITE('\spa');
            IF C<=R THEN WRITE ('\spa')
            END
        ELSE WRITE (S[I])
}


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd;
First draft November 14, 1984

\bye